/*
 * @lc app=leetcode.cn id=875 lang=typescript
 *
 * [875] 爱吃香蕉的珂珂
 */

// @lc code=start

//  思想：二分搜索
//  参考：https://labuladong.github.io/algo/2/21/56/

//  复杂度：O(nlogn) O(1)

function minEatingSpeed(piles: number[], h: number): number {
    // x: 吃香蕉的速度，f(x): 吃香蕉的时间
    const f = (piles: number[], x: number): number => {
        let hours = 0
        for (let i = 0; i < piles.length; i++) {
            hours += Math.floor(piles[i] / x)
            if (piles[i] % x > 0) hours++
        }
        return hours
    }

    let left = 1, right = Math.max(...piles)
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2)
        if (f(piles, mid) <= h) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
};
// @lc code=end

console.log(minEatingSpeed([3, 6, 7, 11], 8))         // 4
console.log(minEatingSpeed([30, 11, 23, 4, 20], 5))   // 30
console.log(minEatingSpeed([30, 11, 23, 4, 20], 6))   // 23
